package Work;

import java.util.Stack;

/**
 * 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
 *
 * 请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
 */
public class Main1 {

        /**
         直接合并数组，使用快排进行升序排序
         */
        public void merge(int[] nums1, int m, int[] nums2, int n) {
            Stack<Integer> stack = new Stack<>();
            
            if(n == 0){
                return;
            }
            for(int i = 0; i < nums2.length;i++){
                nums1[m++] = nums2[i];
            }
            quick(nums1,0,nums1.length - 1);
        }
        //快速排序
        public void quick(int[] nums1,int left,int right){
            if(right < left){
                return;
            }
            int r = reference(nums1,left,right);
            quick(nums1,left,r-1);
            quick(nums1,r+1,right);
        }
        //挖坑法
        public int reference(int[] nums1,int left,int right){
            int tmp = nums1[left];
            int i = left;
            while(left < right){
                while(left < right && tmp <= nums1[right]){
                    right--;
                }
                while(left < right && tmp >= nums1[left]){
                    left++;
                }
                swap(left,right,nums1);
            }
            swap(left,i,nums1);
            return left;
        }
        public void swap(int start,int end,int[] elem){
            int tmp = elem[start];
            elem[start] = elem[end];
            elem[end] = tmp;
        }
}
